// 快速排序 时间复杂度：平均 O(nlogn) 最差 O(n^2) 不稳定 n大时较好
/**
 *
 * @param arr{Array}
 * @param left{number}
 * @param right{number}
 */
function quickSort (arr, left, right) {
    let l = left
    let r = right
    // 中值
    let pivot = arr[~~((left + right) / 2)]
    let temp = 0
    while (l < r) {
        while (arr[l] < pivot) {
            l += 1
        }
        while (arr[r] > pivot) {
            r -= 1
        }
        // 如果l>=r 说明pivot 的左右连边的值 已经按左边全小于pivot 右边全大于pivot
        if (l >= r) {
            break
        }
        temp = arr[l]
        arr[l] = arr[r]
        arr[r] = temp
        if (arr[l] === pivot) {
            r -= 1
        }
        if (arr[r] === pivot) {
            l += 1
        }
    }
    if (l === r) {
        l += 1
        r -= 1
    }
    // 向左递归
    if (left < r) {
        quickSort(arr, left, r)
    }
    // 向右递归
    if (right > l) {
        quickSort(arr, l, right)
    }
}

function main () {
    let arr = [-9, 78, 0, 23, -567, 70]
    quickSort(arr, 0, arr.length - 1)
    console.log(arr)
}

main()
